
/*
回溯
连接：https://leetcode.cn/problems/sudoku-solver/
题目： 填数独


    利用三个数组来标记状态
    因为我们要判断一个数字不能出现在同一行，也不能出现在同一列，并且在同一个九宫格中也不能出现
    所以我们使用bool row[9][10] 来标记任意一行的某个数字是否出现，例如row[2][3]==false就代表在第2行没有出现数字3
    同理 bool col[9][10] 标记任意一列的某个数字是否出现。

    对于9个小九宫格中是否存在相同的数字，我们采用grid[3][3][10]的三维数组进行判断，grid[0][0][1]=false就代表第一个小九宫格中没有数字1
    而grid[i][j]下标让每一个小格子的下标除以3即可得到0-3的下标

    dfs函数如何设计，采用返回值标记填写状态。如果1到9全部填写成功了，那我们就返回true，如果1到9都试过了一边，均不能填写成功，那么就返回false，
    告诉上一层填写这个数字最终无法填写成功，需要从新填写。

*/
class Solution {
public:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]!='.')
                {
                    int num = board[i][j]-'0';
                    row[i][num] = col[j][num] = grid[i/3][j/3][num]=true;
                }
            }
        }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]=='.')
                {
                    for(int num = 1;num<=9;num++)
                    {
                        if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num])
                        {
                            row[i][num] = col[j][num] = grid[i/3][j/3][num]=true;
                            board[i][j] = num+'0';
                            if(dfs(board)==true) return true;//下一层发现填写成功
                            //回溯--恢复现场
                            row[i][num] = col[j][num] = grid[i/3][j/3][num]=false;
                            board[i][j] = '.';
                        }
                        
                    }
                    //9个数字都填完都没有返回到上一层，说明上一层的填写不能形成有效填写
                    return false; 
                }
            }
        }
        //两成循环走完，并且没有遇到'.'说明全部填写成功
        return true;
    }
};